package com.gitee.huxing.algorithmic.daily;

import java.util.*;

/**
 * @Description:
 * @ProjectName: AlgorithmicPactice
 * @Package: com.gitee.huxing.algorithmic.daily
 * @ClassName: CanReorderDoubled
 * @Author: huxing
 * @DateTime: 2022-04-01 10:18 AM
 */
public class CanReorderDoubled {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 3, 6};
        System.out.println(canReorderDoubled(arr));
    }

    public static boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int x : arr) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }
        if (cnt.getOrDefault(0, 0) % 2 != 0) {
            return false;
        }
        List<Integer> vals = new ArrayList<Integer>();
        for (int x : cnt.keySet()) {
            vals.add(x);
        }
        Collections.sort(vals, (a, b) -> Math.abs(a) - Math.abs(b));
        for (int x : vals){
            if (cnt.getOrDefault(2 * x, 0) < cnt.get(x)){
                return false;
            }
            cnt.put(2 * x, cnt.getOrDefault(2 * x, 0) - cnt.get(x));
        }
        return true;
    }
}
